package offer.p111;

import java.util.*;

class Solution2 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 保存变量
        Set<String> variables = new HashSet<>();

        int n = equations.size();
        for (int i = 0; i < n; i++) {
            variables.add(equations.get(i).get(0));
            variables.add(equations.get(i).get(1));
        }

        // 对于每个点（变量），存储其直接连接到的所有点（变量）及对应的权（比）值
        Map<String, List<VariableValue>> adjacencyMap = new HashMap<>();
        for (String variable : variables) {
            adjacencyMap.put(variable, new ArrayList<>());
        }
 
        for (int i = 0; i < n; i++) {
            String varA = equations.get(i).get(0);
            String varB = equations.get(i).get(1);
            adjacencyMap.get(varA).add(new VariableValue(varB, values[i]));
            adjacencyMap.get(varB).add(new VariableValue(varA, 1.0 / values[i]));
        }

        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            String varA = query.get(0);
            String varB = query.get(1);
            if (variables.contains(varA) && variables.contains(varB)) {
                if (varA.equals(varB)) {
                    result = 1.0;
                } else {
                    Queue<String> points = new LinkedList<>();
                    points.offer(varA);
                    Map<String, Double> ratioMap = new HashMap<>();
                    for (String variable : variables) {
                        ratioMap.put(variable, -1.0);
                    }
                    ratioMap.put(varA, 1.0);

                    while (!points.isEmpty() && ratioMap.get(varB) < 0) {
                        String x = points.poll();
                        for (VariableValue variableValue : adjacencyMap.get(x)) {
                            String y = variableValue.variable;
                            double val = variableValue.value;
                            if (ratioMap.get(y) < 0) {
                                ratioMap.put(y, ratioMap.get(x) * val);
                                points.offer(y);
                            }
                        }
                    }
                    result = ratioMap.get(varB);
                }
            }
            ret[i] = result;
        }
        return ret;
    }
}

class VariableValue {
    String variable;
    double value;
    public VariableValue(String variable, double value) {
        this.variable = variable;
        this.value = value;
    }
}